The random 3-satisfiability (3-SAT) problem is in the unsatisfiable (UNSAT)phase when the clause density $\alpha$ exceeds a critical value $\alpha_s\approx 4.267$. However, rigorously proving the unsatisfiability of a givenlarge 3-SAT instance is extremely difficult. In this paper we apply themean-field theory of statistical physics to the unsatisfiability problem, andshow that a specific type of UNSAT witnesses (Feige-Kim-Ofek witnesses) can inprinciple be constructed when the clause density $\alpha > 19$. We thenconstruct Feige-Kim-Ofek witnesses for single 3-SAT instances through a simplerandom sampling algorithm and a focused local search algorithm. The randomsampling algorithm works only when $\alpha$ scales at least linearly with thevariable number $N$, but the focused local search algorithm works for clausedensty $\alpha > c N^{b}$ with $b \approx 0.59$ and prefactor $c \approx 8$.The exponent $b$ can be further decreased by enlarging the single parameter $S$of the focused local search algorithm.
展开▼
机译：当子句密度$ \ alpha $超过临界值$ \ alpha_s \约4.267 $时，随机3-满足性（3-SAT）问题处于不满足（UNSAT）阶段。但是，严格证明给定的大型3-SAT实例的不满足性非常困难。在本文中，我们将统计物理学的主题场理论应用于不满足性问题，并表明当子句密度$ \ alpha> 19 $时，可以构造特定类型的UNSAT证人（Feige-Kim-Ofek证人）。然后，我们通过简单随机采样算法和聚焦局部搜索算法为单个3-SAT实例构造Feige-Kim-Ofek证人。仅当$ \ alpha $至少与可变数$ N $线性比例缩放时，随机采样算法才能工作，但是集中式本地搜索算法适用于子句式$ \ alpha> c N ^ {b} $且$ b \ approx 0.59 $和预因子$ c \约8 $。可以通过扩大聚焦本地搜索算法的单个参数$ S $来进一步减小指数$ b $。
展开▼
